package leetcode.median;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

import leetcode.base.ListNode;

public class $1019_NextLargerNodes {
    public int[] nextLargerNodes(ListNode head) {
        if (head == null) {
            return new int[0];
        }
        ListNode dummy = reverse(head);
        Deque<Integer> stack = new LinkedList<>();
        int[] res = new int[dummy.val];
        int index = dummy.val - 1;
        ListNode tail = dummy.next;
        while (index >= 0) {
            while (!stack.isEmpty() && tail.val >= stack.peek()) {
                stack.pop();
            }
            res[index--] = stack.isEmpty() ? 0 : stack.peek();
            stack.push(tail.val);
            tail = tail.next;
        }
        return res;
    }

    private ListNode reverse(ListNode head) {
        ListNode dummy = new ListNode(-1);
        int len = 0;
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
            len++;
        }
        dummy.val = len;
        dummy.next = prev;
        return dummy;
    }
}
